﻿<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<!-- DW6 -->
<head>
<!-- Copyright 2005 Macromedia, Inc. All rights reserved. -->
<title>设计说明</title>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
<link rel="stylesheet" href="../css/mm_training.css" type="text/css" />
<style type="text/css">
<!--
.STYLE1 {font-size: 12px}
-->
</style>
</head>
<body bgcolor="#64748B">
<table width="100%" border="0" cellspacing="0" cellpadding="0">
  <tr bgcolor="#26354A">
	<td width="15" nowrap="nowrap"><img src="../css/mm_spacer.gif" alt="" width="15" height="1" border="0" /></td>
	<td height="70" colspan="2" nowrap="nowrap" bgcolor="#26354A" class="logo">ABC-DB说明手册</td>
	<td width="25" bgcolor="#26354A">&nbsp;</td>
  </tr>

	<tr bgcolor="#FF6600">
	<td colspan="4"><img src="../css/mm_spacer.gif" alt="" width="1" height="4" border="0" /></td>
	</tr>

	<tr bgcolor="#D3DCE6">
	<td colspan="4"><img src="../css/mm_spacer.gif" alt="" width="1" height="1" border="0" /></td>
	</tr>

	<tr bgcolor="#FFCC00">
	<td width="15" nowrap="nowrap" bgcolor="#FFFF99">&nbsp;</td>
	<td height="24" colspan="2" bgcolor="#FFFF99">
	<table border="0" cellpadding="0" cellspacing="0" id="navigation">
        <tr>
          <td class="navText" align="center" nowrap="nowrap"><a href="../index.html">主页</a></td>
          <td class="navText" align="center" nowrap="nowrap"><a href="requiemention.html">需求规格说明书</a></td>
          <td class="navText" align="center" nowrap="nowrap"><a href="manual.html">系统说明与安装手册</a></td>
          <td class="navText" align="center" nowrap="nowrap"><a href="order.html">系统命令手册</a></td>
          <td class="navText" align="center" nowrap="nowrap"><a href="code.html">设计说明</a></td>
          <td class="navText" align="center" nowrap="nowrap"><a href="exp.html">测试文档</a></td>
          <td class="navText" align="center" nowrap="nowrap"><a href="tutl.html">一个运行实例</a></td>
		<td class="navText" align="center" nowrap="nowrap"><a href="need-imp.html">不足之处</a></td>
        </tr>
      </table>	</td>
	<td width="25" bgcolor="#FFFF99">&nbsp;</td>
  </tr>

	<tr bgcolor="#D3DCE6">
	<td colspan="4"><img src="../css/mm_spacer.gif" alt="" width="1" height="1" border="0" /></td>
	</tr>

	<tr bgcolor="#FF6600">
	<td colspan="4"><img src="../css/mm_spacer.gif" alt="" width="1" height="4" border="0" /></td>
	</tr>

	<tr bgcolor="#D3DCE6">
	<td colspan="4"><img src="../css/mm_spacer.gif" alt="" width="1" height="1" border="0" /></td>
	</tr>

	<tr bgcolor="#D3DCE6">
	<td colspan="3" valign="top"><img src="../css/mm_spacer.gif" alt="" width="35" height="1" border="0" /><br />
	&nbsp;
	<table width="100%" border="0" align="center" cellpadding="2" cellspacing="0">
      <tr>
        <td  class="pageName"><div align="center">设计说明</div></td>
      </tr>
      <tr>
        <td class="bodyText"><hr>
        
         索引目录:<br />
           1.<a href="#one">设计总述</a><br />
           2.<a href="#two">整体模块划分图</a><br />
           3.<a href="#three">各个模块的接口图</a><br />
           4.<a href="#four">线程关系图</a><br />
           5.<a href="#five">整体流程图</a><br />
           6.<a href="#six">共享内存管理模块</a><br />
           &nbsp;&nbsp;6.1.<a href="#six1">共享内存的整体结构</a><br />
           &nbsp;&nbsp;6.2.<a href="#six2">区域一</a><br />
           &nbsp;&nbsp;6.3.<a href="#six3">区域二</a><br />
           &nbsp;&nbsp;6.4.<a href="#six4">区域三</a><br />
           &nbsp;&nbsp;6.5.<a href="#six5">关于区域二和区域三的设计说明</a><br />
           &nbsp;&nbsp;6.6.<a href="#six6">第四区域</a><br />
           &nbsp;&nbsp;6.7.<a href="#six7">第四区域中的块</a><br />
           7.<a href="#seven">共享内存对外接口具体说明</a><br />
           8.<a href="#eight">网络模块</a><br />
           9.<a href="#nine">词法语法解析模块</a><br />
           &nbsp;&nbsp;9.1.<a href="#nine1">并发环境下SQL解析实现</a><br />
           &nbsp;&nbsp;9.2.<a href="#nine2">重要数据结构</a><br />
           &nbsp;&nbsp;9.3.<a href="#nine3">SQL语句的执行过程</a><br />
		<hr>
        
          <h3 align="center" class="STYLE1"><a name="one" id="one"></a>1.设计总述</h3>

            <p class="STYLE1">1.1.本系统除了词法解析部分、语法解析部分外，全部自助开发，未使用任何商业或开源代码。<br />
              其中:<br />
              1.1.1.词语解析部分:<br />
              采用GNU Flex进行自动生成。<br />
              关于Flex，Flex是Lex的另一个替代品,它经常和自由软件Bison语法分析器生成器一起使用。我们预先指定好一些输入词法规则(见server/lex*yacc/lex.y文件)，然后使用Flex读取这个文件，然后自动生成文件flex.yy.c，这个文件是主要由函数yylex()组成，我们在外部调用这个函数，就可以从标准输入中读取我们输入的字符，然后识别。</p>
            <p class="STYLE1"> 1.1.2.语法解析部分:<br />
              采用GNU Bsion进行自动生成。<br />
              维基百科中对Bison的定义:GNU bison是一个自由软件，用于自动生成语法分析器程序，实际上可用于所有常见的操作系统。Bison把LALR形式的上下文无关文法描述转换为可做语法分析的C或C++程序。在新近版本中，Bison增加了对GLR语法分析算法的支持。GNU bison基本兼容Yacc，并做了一些改进。它一般与flex一起使用。<br />
              我们在使用时，预先定义我们一些文法产生式(见server/lex&amp;yacc/parser.y，对于我们这个系统而言，有两部分，一部分是系统命令的文法，用于在系统运行时读取用户输入的操作命令，另一部分是SQL语句的文法)，然后利用GNU Bison针对我们定义的这个语法文件进行生成，生成文件parser.tab.c，这个文件主要由函数yyparse()组成，我们在外部调用这个函数，便可以对标准输入中输入的字符串按我们规定的文法进行解析。</p>
            <p class="STYLE1"> 1.1.3.说明:<br />&nbsp;&nbsp;
            默认的，Flex和Bison生成的词法语法解析文件都是不可重入的，也就是非线程安全的，由于系统要求较高的并发性，我们进行了改写，使得词法语法模块能够可重入，具体可见词法语法解析模块的说明文档。<br />&nbsp;&nbsp;对于产生的词法解析文件，我们未进行较大改动。对于产生的语法文件，我们进行了较大改动，详情见词法语法模块的说明文档。</p>
            <p class="STYLE1">1.2.各个模块之间的接口联系:<br />
              系统的四个模块:<br />
              a.共享内存管理模块<br />
              b.词法语法解析模块<br />
              c.网络与线程模块<br />
              d.锁模块<br />
            </p>
            <p><span class="STYLE1"> 说明:其中,共享内存管理模块是由两个文件实现的:shm.c和shm_interface.c<br />
              我们将共享内存管理模块再次细分为两层:共享内存管理下层和上层，其中下层是最基本的一些操作，这些操作供共享内存管理上层调用，外部模块不得调用共享内存下层操作，只能调用共享内存管理上层中的操作。<br />
              shm.c:这是本系统最为底层的文件，我们称之为共享内存下层管理模块是对共享内存的最底层的管理函数集合，包括创建共享内存，初始化共享内存各个区域，写数据到第一、二、三区域，申请新的数据库，将共享内存数据同步到磁盘上等最基本操作，shm.c文件中的函数全部是供上层 &quot;共享内存上层管理模块调用的&quot;，也就是shm_interface.c文件中的各个函数调用，除此之外，其他模块不得调用shm.c中的函数。<br />
              shm_interface.c:这是共享内存管理的上层操作函数聚合文件，其中定义了许多对外接口，入创建数据库函数，打开数据库函数，插入记录数据库函数，创建表数据库函数，根据给定记录地址，查找下一条记录的函数等等，这些操作相对来说更加“上层一些”，供外部模块调用。</span>
            <hr>

              <h3 align="center">
                <span class="STYLE1"><a name="two" id="two"></a>2.整体模块划分图</span></h3>
          <p class="STYLE1">上面已经说过,整个系统大致分别四个模块,分别是:<br />

                &nbsp;&nbsp;a.客户端\服务端的网络管理模块<br />
                &nbsp;&nbsp;b.词语\语法解析模块<br />
                &nbsp;&nbsp;c.底层对共享内存的管理模块<br />
                &nbsp;&nbsp;d.对于并发,需要对数据加锁管理的锁模块<br /><br />

 四个模块的联系图如下所示:
            <p align="center" class="STYLE1"><img src="code_clip_image002.png" alt="" width="380" height="348" /><br />
            <hr>
              <h3 align="center" class="STYLE1"><a name="three" id="three"></a>3.各个模块的接口图</h3>
            <p class="STYLE1">下图描述了整体系统的各个模块的对外接口，以及各模块之间接口的调用联系。具体各个模块请见各个模块的文档.</p>
              <p align="center" class="STYLE1"><img src="code_clip_image002_0000.png" alt="" width="553" height="463" /><hr />
              <div align="center">
                <h3 class="STYLE1"><a name="four" id="four"></a>4.线程关系图</h3>
            </div>
            <p class="STYLE1">下图描述了系统运行之后，各个子线程的联系以及各线程的功能图。 系统进程中各子线程的关系: </p>
              <p align="center" class="STYLE1"><img src="code_clip_image002_0001.png" alt="" width="557" height="474" /><hr>
              <div align="center">
                <h3 class="STYLE1"><a name="five" id="five"></a>5.整体流程图</h3>
            </div>
            <p class="STYLE1">下图描述了系统运行时，各个部分是怎样相互协作运行的。</p>
              <p align="center" class="STYLE1"><img src="code_clip_image002_0002.png" alt="" width="560" height="555" /></p>
              <p><br />
                <span class="STYLE1">说明:<br />
              不管是服务端还是客户端，都需要等待用户输入，用户输入的指令分两种:</span></p>
              <span class="STYLE1">1.管理指令              </span>
              <p class="STYLE1">指管理系统的命令，如打开数据库open,移除数据库removedb,创建数据库createdb,查看帮助文件help等等。这些指令中很大一部分是只能在服务端执行的，客户端是无法运行的，具体见使用说明文档。 </p>
              <span class="STYLE1">2.SQL语句指令              </span>
              <p class="STYLE1">指的是标准的SQL语句，对当前打开着的数据库的一些操作，不如创建新的表create，查询select等等，具体见使用说明文档。SQL语句命令在服务端和客户端都可以执行，没有分别。 </p>
              <p class="STYLE1">用户输入一条指名后的流程:<br />
                1.服务端(客户端)等待用户输入指令,用户输入一条指定,以分号(;)结尾，按下回车.<br />
                2.服务端:指令直接以一个字符串形式传递给语法解析函数yyparse().<br />
                客户端:指令以一字符串格式通过socket传递给指定服务器,服务器相应的线程接收到指令后转交给语法解析函数yyparse().</p>
              <span class="STYLE1">3.语法解析函数yyparse()接收到指令字符串后开始解析，期间会不断调用词法解析函数yylex()来获取获取指令字符串中的各个字符。语法解析函数一边解析指令字符串，一边产生执行相应的操作，我们把这一层成为逻辑管理层，逻辑管理层根据语法解析的结果调用执行相应的系列函数来完成对应的工作，在这期间，逻辑管理层能够对磁盘、共享内存等进行统筹管理，当最终操作完成，逻辑管理层将结果输入到指定的地方。</span><hr>
              <h3 align="center"><span class="STYLE1"><a name="six" id="six"></a>6.共享内存管理模块</span><br />
            </h3>
            <p class="STYLE1">当本系统服务端创建或者打开某一数据库时，根据用户在创建此数据库时指定的大小，进程向系统申请一定大小的共享内存。具体申请的大小分两部分，一部分是用户创建此数据库时指定的存放数据的大小，另一部分是需要存放数据字典信息的固定大小(下文会说明)。若申请成功，则申请到的共享内存自动绑定到进程中。 <br />
            本文档讲解系统如何管理使用所申请到的共享内存，如果将其逻辑划分，使其效率更高。 </p>
              <h2 class="STYLE1"><a name="six1" id="six1"></a>6.1.共享内存的整体结构</h2>
              <p class="STYLE1"> 
                逻辑上进程将共享内存进行分区，具体分为四个区域，分别是:
            <ul>
              <li class="STYLE1">区域一:数据库信息区 </li>
              <li class="STYLE1">区域二:表信息区 </li>
              <li class="STYLE1">区域三:列信息区 </li>
              <li class="STYLE1">区域四:数据区 </li>
            </ul>
                <span class="STYLE1">如下图:
                </p>
                </span>
            <div align="center"><img src="code_clip_image002_0003.png" alt="" width="306" height="370" /><br />
              </div>
              <h2 class="STYLE1"><a name="six2" id="six2"></a>6.2.区域一 </h2>
              
                <span class="STYLE1">区域一存放数据库的信息,具体是存放一个数据库结构体变量DB,其结构体如下:<br />
                Struct  DB {<br />
&nbsp;&nbsp;char  *db_name;  //数据库名称 <br />
&nbsp;&nbsp;long  db_size;     //创建数据库时指定的数据库大小,单位是bytes<br />
&nbsp;&nbsp;char  *pwd;      //数据库密码 <br />
                };
                </p>
                </span>
              <p class="STYLE1">因此区域一其实就是一个DB结构体实例。 <br />
              它总是由全局DB类型指针<strong>ptr_db</strong>指向。 </p>
              <p class="STYLE1">因此如果程序要得到当前数据库的密码，只需要使用如下方式: ptr_db-&gt;pwd。 </p>
              <h2 class="STYLE1"><a name="six3" id="six3"></a>6.3.区域二 </h2>
             
                <span class="STYLE1">系统中有一结构体TB，表示每张表:<br />
                Struct  TB{<br />
                int  id;              //数据表的id<br />
&nbsp;&nbsp;char  *tb_name;      //数据表名称 <br />
&nbsp;&nbsp;int  num_of_column;  //本表所含的列数目(属性数目)<br />
&nbsp;&nbsp;void  *first_block;     //指向本表第一个块的偏移量 <br />
&nbsp;&nbsp;void  *useable_block;  //指向第一个有空闲的可用块的偏移量 <br />
                };<br />
                区域二存放当前数据库的所有数据表信息，也就是TB结构体实例。 <br />
                系统中有一全局常量(用户可根据需要自行修改)NUM_OF_TB，其值是数据库最多可有的数据表的数目，区域二预设NUM_OF_TB个TB结构体。假设其值为20，则当前数据库最多能有不超过20张表，也就是区域二预设有20个TB结构体实例，区域二起始地址由TB型指针<strong>ptr_tb</strong>指向之，假如要获得id为5的表的信息，则只需要使用指针  (ptr_tb+5)。 
                </p>
              预设最多有20张表的区域二示意图:              </span>
              <p align="center"><span class="STYLE1"></span><br />
                  <img src="code_clip_image002_0004.png" alt="1" width="193" height="190" /></p>
              <h2 class="STYLE1"><a name="six4" id="six4"></a>6.4.区域三 </h2>

                <span class="STYLE1">同样，系统中有代表列属性的结构体COLU:<br />
                Struct  COLU {<br />
&nbsp;&nbsp;int  id;            //列id<br />
&nbsp;&nbsp;char  *colu_name;  //列属性名称 <br />
&nbsp;&nbsp;int  *length;       //限长 <br />
&nbsp;&nbsp;int  type;         //0代表char *,1代表int,2代表float,初为-1<br />
                };<br />
                在此需要说明的是限长length.本程序的存储方式是将所有的数据信息以字符串形式存入内存，所以如果有一整形类型，值为100，则其在内存中的形式是&quot;100&quot;，实际占4个字节(包含末尾的'\0'),而非以二进制补码形式存放。 <br />
                系统中同样有一全局变量NUM_OF_COLU，规定了每张表最多所含的列数目(类似于区域二中的表)，所以实质上区域三一共有NUM_OF_TB * NUM_OF_COLU个COLU结构体实例。在此假设NUM_OF_TB和NUM_OF_COLU均为20，则区域三一共有20*20=400个结构体，第0～19个COLU结构体属于表0，20～39属于表1，以此类推。 <br />
                假设预定20张表，每个表20列，第三区域示意图:
                </p>
                </span>
              <p align="center"><br />
                <img src="code_clip_image004.png" alt="2" width="303" height="589" /></p>
              <p><br />
                <span class="STYLE1">系统中固定有一个COLU类型的指针<strong>ptr_colu</strong>指向第三区域起始。因此只要知道表的id,就可以使用如下方法访问到其属性信息: ptr_colu + NUM_OF_COLU*tb_id</span></p>
              <p>&nbsp;</p>
              <h2 class="STYLE1"><a name="six5" id="six5"></a>6.5.关于区域二和区域三的设计说明 </h2>
             
                <span class="STYLE1">6.5.1.采用固定的，类似数组的方式设计区域二和三，而不是采用动态的数据结构(比如链表)，是基于以下考虑： <br />
                &nbsp;&nbsp;a:一般来说，数据库的表的数目和列的数目在创建时都是固定的，很少有改动，特别是属性.<br />
                &nbsp;&nbsp;b:这样设计能够快速定位想要访问的某个表或者某个表的某个列，访问方法如下:若已知欲访问的表的id，则指向表的结构体的指针为(ptr_tb + id)，若已经表的tb_id和列的colu_id，则访问这一列的方法为(ptr_colu  + tb_id*NUM_OF_TB + colu_id)。于是访问的效率由链表的O(n)减小到O(1)。 <br />
                &nbsp;&nbsp;c:对于这样设计的一个缺点”表和列的最大数目的固定造成的不灵活性”，我们是这样认为的:由于内存数据库的使用一般是特定某些场合，具有较高的针对性，所以我们完全可以了解预测大概需要创建的表的数目和列的数目，于是，时间换空间在这里能够很好的理解。 <br />
                6.5.2.一般来说，第一、二、三区域的大小是固定的.<br />
                总大小为=sizeof(DB) + sizeof(TB)*NUM_OF_TB + sizeof(COLU)*NUM_OF_COLU 字节。 
                </p>
                </span>
                <h2 class="STYLE1"><a name="six6" id="six6"></a>6.6第四区域 </h2>

                <span class="STYLE1">6.6.1.第四区域用于存放数据记录,是整个共享内存中的核心区域，一般来说也是最大的一个区域，相对于第一、二、三区域来说，第四区域的大小是可变的，每个数据库都不一样，这个区域的大小是由用户在创建数据库的时候指定的，至此可以明白，进程向系统申请的共享内存的大小是由两部分组成:一部分是固定的一二三区域大小，另一部分是用户输入的大小(第四区域)，用户输入的大小仅仅是第四区域的大小。 <br />
                6.6.2.为了便于管理，本区域需要进行分块，每块的大小由全局变量BLOCK_SIZE指定，默认是2048字节，假设用户输入的大小是db_size字节，那么总的块的数目可以计算得到 db_size/BLOCK_SIZE块。 <br />
                第四区域示意图:
                </p>
                </span>
              <p align="center"><br />
                <img src="code_clip_image006.png" alt="3" width="126" height="237" /></p>
              <h2 class="STYLE1"><a name="six7" id="six7"></a>6.7第四区域中的块 </h2>
                <span class="STYLE1">6.7.1.块的结构:<br />
                Struct  BLOCK {<br />
&nbsp;&nbsp;BLOCK_HEAD  head;                      //块头部 <br />
&nbsp;&nbsp;char  data[BLOCK_SIZE-sizeof(BLOCK_HEAD)];  //数据部分 <br />
                };<br />
                其中的块头部结构如下 <br />
                Struct  BLOCK_HEAD {<br />
&nbsp;&nbsp;void  *pre;                //相关联的前一块 <br />
&nbsp;&nbsp;void  *next;               //相关联的下一块 <br />
&nbsp;&nbsp;int  tb;                   //块所属表 <br />
&nbsp;&nbsp;unsigned  long record_size;  //记录本块内存储的记录的最大大小 <br />
&nbsp;&nbsp;int  unused;              //记录块内还能存储多个条记录 <br />
&nbsp;&nbsp;int  useable_offset;        //块内可用的空闲记录的位移量 <br />
                };<br />
                6.7.2.首先，每个块存放一定数量的记录，其存放的记录只能属于同一张表，也就是说，不能在一个块里面混杂存放不同表的记录。 <br />
                6.7.3.每个块分为两部分:块头部和数据部分.块头部存放本块的一些信息数据，比如相关联的前一块的指针和相关联的下一块的指针，这个&quot;相关联&quot;指的是同属一张表的各个块，在区域二的介绍中，每个表结构体中有一个成员first_block，它指向本表的第一个块，简称块一，块一中的头部中的next指向下一块，简称块二，于是同一张表的各个块就链接起来了。头部中的tb表明了本块所属的表的id,record_size告诉了本块存储的记录的长度，也就是各个属性的length的总和，于是，每个块能够存储本表的记录数就可以计算而得:(BLOCK_SIZE -  sizeof(BLOCK_HEAD))/record_size。unused指明了本块目前可以插入多少条记录useable_offset指明了首个可查入记录的空闲地址的偏移量。 <br />
                6.7.4.数据部分就是一个字符数组。 <br />
                6.7.5.在内存中,每条记录的形式是一个字符串,例如:<br />
                表的关系是id(integer,10),name(varchar,50),grade(double,10)<br />
                那么，在每个块内，给每条记录预留的空间大小事10+50+10+1=71字节()外加末尾的0，所以如果有一条记录(1,Li Ming,80.5),其在内存中的存储形式就是“0，Li Ming,80.5 ...”,最后的…表示剩余的空白字符。于是如果将这条记录插入到一个空白的表中，那么在这个表的第一个块的data区，其data[0]-data[70]总共71个字节，便存放了这条记录，以后插入的第二条记录，便是data[71]-data[142],以此类推。于是，在首部结构中的useable_offset指的偏移量就是这个0或者71,或其他。 <br />
                <br />
                例中记录的存储结构:
                </p>
                </span>
              <p align="center"><br />
                <img src="code_clip_image008.png" alt="4" width="407" height="121" /></p>
              <p><br />
                <span class="STYLE1">Data区域存储多条记录结构:</span></p>
              <p align="center"><br />
                <img src="code_clip_image010.png" alt="5" width="544" height="171" /></p>
              <p align="left" class="STYLE1">最后，还有一点是关于在系统设计中，记录地址的格式问题:<br />
              由以上可以得知，共享内存将第四区域进行块的划分，然后每个块内部的data区存放相同大小的各条记录，那么也就是说，要定位到具体一条记录，需要知道1:记录所在块的地址.2:记录在该块内部的data区中的偏移量.因此我们在全局头文件data区域定义了一个块地址的结构体record_add： <br />
              typedef struct{<br />
             BLOCK  *p_blk;  //块地址<br />
           int off;       //data[off],即偏移量<br />
           }record_add;<br />
            有了这个结构体，我们在具体的设计过程中，就可以很方便的传递具体记录的地址了。<hr>
              <h3 align="center"><span class="STYLE1"><a name="seven" id="seven"></a>7.共享内存对外接口具体说明</span>
                  </p>              
              </h3>
            <p><br />
              <span class="STYLE1">本段文档讲解共享内存数据库每个操作(例如创建一个数据库，创建一个表，插入一条记录等)的执行的具体流程。 </span></p>
              <p class="STYLE1"><a name="seven1" id="seven1"></a>7.1.创建数据库 <br />
                当用户输入命令createdb后，语法解析调用create_db()函数，然后在这个函数中:<br />
                1:获得用户的键盘输入(db名称,共享内存大小,密码).<br />
                2:调用db_get_shmm(size_t),传入参数是步骤1中的共享内存大小,来创建共享内存.<br />
                3:共享内存创建成功之后调用db_init_shmm()函数,初始化共享内存各个区域(主要是初始化各个全局指针).<br />
                4:调用db_insert_db_info(char  *db_name,unsigned long size,char *pwd),来初始化区域1.<br />
                5:至此创建完一个数据库,此时区域1初始化完毕,区域2、3、4为空白 </p>
              <p class="STYLE1"><a name="seven2" id="seven2"></a>7.2.移除数据库(remove)<br />
                用户欲移除当前数据库，打开另外的数据库时，需要输入removedb，语法解析器调用removedb()函数:<br />
                1:调用shmm_at(),传递IPC_RMID和共享内存的id过去，就可以将指定共享内存从当前进程中脱绑并删除。 </p>
              <p class="STYLE1"><a name="seven3" id="seven3"></a>7.3.打开数据库 <br />
                用户输入命令open后，语法解析器调用open_db()函数： <br />
                1.open()函数获取用户输入的所要打开的数据库的名称及密码 <br />
                2.然后在磁盘上找到对用的数据库的字典文件，检查密码是否正确，无误后跟据字典中所定义的数据库的大小，创建相应的共享内存，初始化第一、二、三区域。并读取相应表的数据文件，将这些文件中的记录数据导入共享内存。 </p>
              <p class="STYLE1"><a name="seven4" id="seven4"></a>7.4.创建表 <br />
                语法解析部分获得创建数据库的各个参数后，调用CreateTable(Table *T):<br />
                1.调用db_insert_tb_info(char  *tb_name,int num_of_colu)在第二区域插入一个tb结构体,成功返回新创建的tb_id.<br />
                2.调用db_insert_colu_info(int  tb_id,char *column_name,int length,int type)在区域3中插入一个新的列.<br />
                3.在区域2中创建完一个新的表结构后,调用db_require_new_block(int  tb_id,int colu_id)来为刚刚创建的表申请一个新的数据块,传入参数是表的id和属性的id(一般为-1).</p>
              <p class="STYLE1"><a name="seven5" id="seven5"></a>7.5.删除表 <br />
                1.语法解析器得到要删除的表的名称.<br />
                2.查找到表对应的id号.<br />
                3.调用delete_tb(int  tb_id),该函数将第二、三、四区域中相关联的结构体、数据库的相关位置-1，以此表明删除。 </p>
              <p class="STYLE1"><a name="seven6" id="seven6"></a>7.6.遍历某一表的所有记录:<br />
                1:调用ExistTable(char  *table_name)获取相应的表tb_id<br />
                2:调用Get_First_Record(int  tb_id)获得此表第一条记录的地址(地址形式是record_add结构体)<br />
                3:循环调用Get_Record(record_add  , Record *),第一个参数是本次要访问的记录的地址,函数的返回值是下一条记录的地址,所以大致循环结构是:<br />
                while((rd_add=Get_Record(rd_add,*record)) !=  NULL){<br />
                //处理 <br />
                }</p>
              <p class="STYLE1"><a name="seven7" id="seven7"></a>7.7.插入一条记录:<br />
                1:创建一个Record类型的结构体(每个字段的数据填充好).<br />
                2:调用Combine_Record_To_String(Record  *,Char *content),第一个参数是步骤1中的Record结构,第二个参数是一个空字符串数组.<br />
                3:调用db_insert_record(char  *content,int tb_id),第一个参数是步骤2中的字符串数组,第二个参数是所插入记录所属的表id.</p>
              <p class="STYLE1"><a name="seven8" id="seven8"></a>7.8.删除记录:<br />
                1:遍历某一表,查找到所要的记录,记下记录的地址record_add.<br />
                2:调用Delete_Record(record_add),参数是步骤1中找到的记录的地址.</p>
              <p class="STYLE1"><a name="seven9" id="seven9"></a>7.9.修改记录:<br />
                1:遍历某一表,找到所要修改的记录地址.<br />
                2:调用Update_Record(record_add,Record  *),第一个参数是所要修改记录的地址,第二个参数是新的记录内容(包含所有字段,而非仅仅需要修改的字段)</p>
              <p class="STYLE1"><a name="seven10" id="seven10"></a>7.10.关于一些具体的算法 <br />
                设共享内存大小是M字节，块大小是N字节，则一共存在M/N个块，每个块存放同一张表的数据，设表A的记录长度最大是S字节，那么，简单化的说，每个块可以存放N/S条记录(不考虑块头部的信息)。 <br />
                同一张表的各个块之间通过块首部的指针相连接。每块的块首部有一位指示本块所属的表的表id,若是空闲块，则此位是-1,数据库初始化时，整个第四区域的所有块进行初始化，每个块的表id字段都初始化为-1，待到分配某一块给某一表时8，再修改这个位。第二区域中的表结构中，有一个成员指针指向本表的“第一个块”。 <br />
            全局指针中，有一个指针是ptr_blk,这个指针总是指向第四区域起始地址。另有一指针ptr_blk_curr指针，指向的是前一次分配的块的下一块地址(如果前一次分配的是区域中的最后一块，则ptr_blk_curr指回区域的第一个块)。 </p>
              <p class="STYLE1"><a name="seven11" id="seven11"></a>7.11.插入记录流程 <br />
                由shm_interface.c中的int insert_record(char *content,int tb_id)函数实现:<br />
                1准备好要插入的记录的字符串形式(可以经Combine_Record_To_String()函数转换)，和要插入记录所属表的id.。 <br />
                2.调用insert_record(char *content,int tb_id)函数。 </p>
              <p class="STYLE1">插入记录的具体过程:<br />
                1.每张表的结构体中有一成员变量useable_block，该变量总是指向本表所有的块中，有空闲空间的块的地址(也就是这块还没满，有剩余，可以再插入记录)。获得这个变量，进而获得可插块的指针。 <br />
                2.访问第1步所获得块，每个块的首部结构中，有一变量useable_offset，就是说如果这个块的data区还有可用空间，则这个变量指名了这个可用空间的起始偏移量。访问这个变量，获得插入的起始偏移量。 <br />
                3.将记录复制到这个位置。完成插入。 <br />
                4.由于插入了一条记录，故要修改相应的标志。 <br />
                5.需要修改所在块的unused变量(这个变量指名了这个块还可以插几个记录)，将unused减1。 <br />
                6.调用find_free_space(int tb_id,record_add curr)函数，传递刚刚插入的记录的地址结构，和所属表id.这个函数用来查找下一个可插入的块的地址和块内偏移。 <br />
                7.在find_free_space()函数中，先检查在刚刚所插入的块的首部的unused变量，如果大于0，则仅仅需要修改首部信息中的useable_offset，指向空闲的起始地址。 <br />
                8.如果小于0，则表明本块已经满了，需要查找到另外一个有空余的块，以备下一次插入记录时所用。于是从当前块的下一块开始查找。 <br />
                9.检查块的首部的tb是否是所要的表，如果不是，则查找下一块，否则检查这个块的首部的unused,如果大于0，则将这块的地址登记到所属表的useable_block，然后完成。如果小于0，则继续查找下面一块。 <br />
                10.如果目前已经申请的所有的块都已经满了，则需要申请一个全新块，则调用申请块函数，将申请到的块的地址等级到表所属的useable_block中。 <br />
                11.完成 </p>
              <p class="STYLE1"><a name="seven12" id="seven12"></a>7.12.删除记录 <br />
                由void Delete_Record(record_add rd)函数实现，传递的参数是所要删除的记录的地址结构:<br />
                1.将记录在块内的起始第一个字节设置为0,表示这条记录为空.<br />
                2.将这个块首部的unused减1，表示这个块的记录减少了一条。 <br />
                3.设这个块一共可以插入n条记录，如果unused=n，则说明这个块目前已经没有记录了，可以将其释放。 <br />
                4.简单的将这个块的首部的tb设为-1，表明这个块已经被释放，然后将这个块的前一块(后一块)首部中指向本块的指针修改。 </p>
              <p class="STYLE1"><a name="seven13" id="seven13"></a>7.13.块申请分配算法 <br />
                由shm.c文件中的_require_new_block(int tb_id)函数实现:<br />
                1.调用_require_new_block(int table_id)函数，传递所要申请的块所属的表的id,简称tb_id.<br />
                2.检查ptr_blk_curr所指向的块的头部的tb成员(此成员变量指名这一块是空还是已经分配给某个表了，如果是空，则改成员变量值是-1，如果已经分配给某个表了，那么值是所属表的id)。 <br />
                3.如果tb是-1，则表示这个块是空闲块，那么就分配这个块。 <br />
                4.如果不是-1，说明这个块已经分配给某个表了。 <br />
                5.如果循环查找了一遍，没有找到空闲块，那么返回出错，表示已经没有空闲块可用了。 <br />
                6.否则对查找到的空闲块进行初始化，然后返回其地址。 <br />
                7.将ptr_blk_curr指向指向下一块。 </p>
              <p class="STYLE1"><a name="seven14" id="seven14"></a>7.14.块回收算法:<br />
                1.只需要简单地将所在块的首部的tb成员变量设为-1，即代表这个块空闲。<hr>
                <h3 align="center" class="STYLE1"><a name="eight" id="eight"></a>8.网络模块</h3>
            <p class="STYLE1">本系统分别客户端和服务端，服务端能够创建打开删除各个数据库，并能对各个数据库进行各种查询等操作。客户端仅能够对服务端已经打开的数据库使用SQL语句进行查询等操作。 </p>
                <p class="STYLE1">服务端:<br />
                服务端的主程序是多线程的，当程序启动之后，系统自动产生一个线程a,用来响应服务端本地操作命令，主线程则监听相应端口，等待外部连接，等到有外部客户端连接，则自动产生一个线程b，响应外部的客户端连接请求，主线程则继续监听。 </p>
                <span class="STYLE1">示意图如下:                </span>
            <p align="center" class="STYLE1"><img src="code_clip_image002_0005.png" alt="" width="317" height="442" /></p>
            <span class="STYLE1">客户端:客户端调用服务端提供的api接口，首先与服务端建立连接，然后等待客户端用户输入命令，将命令送往服务端，并等待结果，每个结果以三个回车\n\n\n为结束符，客户端接收 数据时，如果遇到连续的3个回车符，则接收完毕。</span> <hr>
            <h3 align="center" class="STYLE1"><a name="nine" id="nine"></a>9.词法语法解析模块</h3>
            <p><br />
              <span class="STYLE1">内存数据库系统在外部接口方面，为了能够有效地支持用户的SQL语句查询操作，需要设计并实现对SQL语句的解析功能，以便能够更广泛地支持用户对数据库的操作。本系统通过设计词法解析模块以及语法解析模块，实现对用户所输入SQL语句的词法检查、语法分析以及执行SQL语句的功能。 <br />
            设计的基本思想：运用代码生存工具flex以及bison，编写相应的词法解析文件lex.l(LEX[1]源文件)以及语法解析文件parser.y(YACC[2]源文件)，并在语法分析过程中完成相应的语义分析过程。在进行词法以及语法分析结束后调用相应的SQL执行程序，对内存数据进行操作并将结果返回。 </span></p>
            <p class="STYLE1"><strong><em><a name="nine1" id="nine1"></a>9.1.并发环境下SQL解析实现：</em></strong><br />
  在多用户的并发环境下，默认的词法解析程序和语法解析程序联合使用时，两者间通过设置一些全局静态变量来保存解析过程中的状态，并通过这些静态变量来交换信息，因此，一般的词法语法解析程序都是不可重入的（线程不安全的函数）。为了保证多个用户线程能够安全地调用SQL语句解析程序，本系统对原有的词法语法解析程序做了大量修改，在运用flex&amp;bison[3]对词法语法文件进行编译生成过程中添加一些可重入的选项，并重新定义了解析的入口函数yyparser（）、YY_INPUT、yyerror（）等重要函数。通过向解析函数显示地传递参数、将原来的全局静态变量变为函数内部的局部变量并通过传递参数的方式来完成词法解析程序与语法解析程序的交互，最终实现一个可重入的SQL解析程序以提供给多个用户线程调用。 </p>
            <p class="STYLE1"><strong><em><a name="nine2" id="nine2"></a>9.2.重要数据结构：</em></strong><br />
              为了能够执行SQL语句，本系统通过设计一种类似语法树的数据结构来实现SQL语句解析过程与SQL语句执行过程的交互。针对SQL语句自身的特点，由于本系统仅实现基本的SQL语句，一个典型的SQL语句主要包括所要操作的表、选取的字段、过滤条件等组成部分。 </p>
            <p class="STYLE1">1 Field结构体，定义一个字段的结构体： <br />
              Typedef struct Field<br />
              {<br />
              所属表的名称； <br />
              字段名； <br />
              字段的值；//整型、浮点型、字符串 <br />
              字段的类型；//枚举类型 <br />
              指向下一字段的指针； <br />
              ……<br />
              }Field;</p>
            <p class="STYLE1">2 Table结构体，定义一个表的信息结构体： <br />
              typedef struct Table<br />
              {<br />
              表名称； <br />
              表中首字段的指针； <br />
              表中尾字段的指针； <br />
              表中字段的数目； <br />
              指向下一表的指针； <br />
              ……..<br />
              } Table;<br />
              3 Where结构体，定义一个过滤条件的结构体： <br />
              typedef struct<br />
              {<br />
              Wher语句的类型 ；//enum {AND,OR} 用and连接的条件或用or连接的条件 <br />
              指向WhereTable结构的指针;</p>
            <p class="STYLE1">}Where;<br />
              4 WhereTable结构体,定义与一张表相关的过滤条件的集合:<br />
              typedef struct WhereTable<br />
              {<br />
              相关表的名称;<br />
              指向首个过滤结节点Where_node的指针； <br />
              指向最后一个过滤结节点Where_node的指针； <br />
              指向下一个WhereTable结构的指针； <br />
              过滤节点链表的长度； </p>
            <p class="STYLE1">} WhereTable;<br />
              5 Where_node结构体，定义一个过滤节点： <br />
              typedef struct Where_node<br />
              {<br />
              查询表的名称； <br />
              过滤节点的左子节点； <br />
              过滤节点的右子节点； <br />
              比较的类型；//枚举类 &gt; &lt; = ;<br />
              指向下一个过滤节点的指针； <br />
              } Where_node； <br />
              其中，where过滤条件可以采用如下的形式表示： <br />
              <img src="code_clip_image002_0006.png" alt="11" width="424" height="176" /> <br />
              对于不同的SQL语句，本系统所设计SQL语法以及所构建的相应语法树结构如下： <br />
              创建数据表：<strong>Create</strong> <strong>Table</strong> table_name (Field1 Date_Type leng, Field2 Date_Type leng … );<br />
              <img src="code_clip_image004_0000.png" alt="22" width="465" height="91" /> <br />
              删除数据表：<strong>Drop</strong> table_name;<br />
              <img src="code_clip_image006_0000.png" alt="33" width="167" height="69" /> <br />
              添加记录：<strong>Insert Into</strong> table_name <strong>Values</strong> (value1,value2 … );<br />
              <strong>Insert Into</strong> table_name (Field1,Field2…)<strong>Values</strong> (value1,value2 … );<br />
              <img src="code_clip_image008_0000.png" alt="44" width="553" height="98" /> <br />
              修改记录：<strong>Update table</strong>_name <strong>Set</strong> Field1 = values，Field1 = values .. <strong>Where</strong> a opt b <strong>And</strong> a2 opt  b2 …;<br />
              <img src="code_clip_image010_0000.png" alt="55" width="507" height="231" /> <br />
              删除记录：<strong>Delete From </strong>table_name <strong>Where</strong> a opt b <strong>And</strong> a2 opt b2 …;<br />
              <img src="code_clip_image012.png" alt="66" width="436" height="212" /> <br />
              查询记录： <strong>Select</strong> Field1 ,Field2, … <strong>From</strong> Table <strong>Where</strong> a opt b <strong>And</strong> a2 opt b2 …;<br />
              <img src="code_clip_image014.png" alt="77" width="468" height="254" /> </p>
            <p>&nbsp;</p>
            <p class="STYLE1">下面给出详细的SQL语句解析过程： </p>
            <table border="1" cellpadding="0" cellspacing="1" bordercolor="#996699">
              <tr>
                <td width="38" class="STYLE1"><br />
                  步骤1 </td>
                <td width="533"><p class="STYLE1">读入用户或管理员所输入的SQL语句或其他命令语句（解析同时包括对输入命令的解析，以下重点描述有关SQL语句的部分） </p></td>
              </tr>
              <tr>
                <td width="38"><p align="center" class="STYLE1">步骤2</p></td>
                <td width="533"><p class="STYLE1">系统调用解析语句的入口函数parse（），并传递一个sql_sentence结构，该结构包含了描述不同语句的语法树根节点指针、用户的套接字接口以及计时变量等信息。 </p></td>
              </tr>
              <tr>
                <td width="38"><p class="STYLE1">步骤3</p></td>
                <td width="533"><p class="STYLE1">parse函数首先调用此法解析的入口函数yylex进行词法分析。 </p></td>
              </tr>
              <tr>
                <td width="38"><p class="STYLE1">步骤4</p></td>
                <td width="533"><p class="STYLE1">在词法分析过程中，匹配每一个输入的字符并检查输入语句有无拼写错误，然后将匹配的字符传递给语法解析过程。 </p></td>
              </tr>
              <tr>
                <td width="38"><p class="STYLE1">步骤5</p></td>
                <td width="533"><p class="STYLE1">语法解析过程接收传递过来的合法字符后，进行相应的语法分析，检查是否符合某一条SQL语句。在语法分析的同时，进行对应的意义动作分析，构建上面所描述的语法树，并检查字段、表是否存在，以及其他一些约束限制。 </p></td>
              </tr>
              <tr>
                <td width="38"><p class="STYLE1">步骤6</p></td>
                <td width="533"><p class="STYLE1">重复执行步骤4、5，直到全部扫描输入的每一个字符，或出现语法错误或语义错误而结束。 </p></td>
              </tr>
              <tr>
                <td width="38"><p class="STYLE1">步骤7</p></td>
                <td width="533"><p class="STYLE1">如果输入的语句正确，则利用解析过程中所构建的语法树执行相应的SQl语句。 </p></td>
              </tr>
            </table>
            <p class="STYLE1">1 词法解析模块 ： <br />
              功能：扫描用户或服务端输入的SQL语句并进行词法分析，检查有无拼写错误或非法字符，将匹配的字符传递给语法解析模块直到结束或出错。 <br />
              实现方法：本系统在Unix/Linux环境下，通过编写描述词法规则的lex[2]文件，利用flex工具自动生成相应的词法解析文件lex.yy.c。 </p>
            <p class="STYLE1">2 语法解析模块： <br />
              功能：从词法解析模块中接收匹配的字符，根据预先定义好的语法规则进行解析，并同时进行语义检查、执行相应的语义动作以及构造对应的语法树结构。 <br />
              实现方法：根据yacc[3]所规定的语法规则，够着符合本系统所需要的SQL文法、产生式。在Unix/Linux环境下运用bison工具产生需要的语法解析文件parser.yy.c以及头文件parser.tab.h。 </p>
            <p>&nbsp;</p>
            <p class="STYLE1"><strong><a name="nine3" id="nine3"></a>9.3.SQL语句的执行过程：</strong> <br />
              通过词法分析、语法分析以及语义检查，最终产生一个对应的SQL语法树结构，下面要做的即是利用每个语句所对应的树结构体，对内存数据库进行访问，并执行具体的查找记录、删除记录等操作。 <br />
              传统的基于磁盘的SQL查询计划是否复杂，有基于查询规则的和基于查询代价的两种策略。但本系统是以内存为基础的数据库，在查询速度以及数据传送率上都远远胜于磁盘数据库，应在搜索时间以及空间消耗上做出权衡。本系统目前仅支持单表查询，采用“全表扫描”方法完成SQL的查询过程。该方法的最大特点便是简单、有效、容易实现，对于磁盘数据库来说，由于大量的I/O时间“全表扫描”无疑是一种最低效的查询执行策略！但基于内存的数据库系统由于将数据存储在内存中，大大缓解了数据传输的压力。传统数据库体系为了提高数据检索的效率，为数据表的部分字段创建了索引，本系统未建立索引功能，对数据表的所有查询动作全部基于“全表扫描”方法。 <br />
              对于含有where查询条件的SQL语句，对记录的查询过程如下：<br />
              （1）从主存中获得相关数据表的首记录地址，并根据where条件中所涉及到的相关比较字段，从主存中读取这些字段的数据内容。 <br />
              （2）根据语法解析过程中所形成的语法树，获取where过滤条件的内容，并与真实数据比较、检查。若不满足过滤条件，则执行步骤（4）；否则，执行下一步操作。 <br />
              （3）对于不同的语句各自执行相应的动作：如&nbsp;查询语句则需要根据用户选择的输出字段，从主存中读取该记录的相应字段数据，并显示输出；若是跟新语句或删除语句，则调用下层接口对主存中该记录进行跟新或删除操作。 <br />
              （4）继续读取下一条记录的相关字段信息，直到最后一条记录为止。 </p>            </td>
      </tr>
    </table>
	<br /> 	<br />	</td>
	<td>&nbsp;</td>
	</tr>

	
</table>
</body>
</html>

